#include <stdio.h>
#include <stdlib.h>
/**
 * ( () () () () () () () {} {} {} [] [] {} )
 * 类似于编辑器的括号匹配检测
 * 步骤
 *    1. 从左往右依次扫描 遇到左括号就把左括号压入栈中
 *    2. 遇到右括号就从栈顶弹出一个左括号进行匹配
 *    3. 左右括号是同个类型的就匹配成功 反之失败
 *    4. 可能出现的问题: 栈空 或 栈满
 * */

#define MAXSIZE 10

typedef char ElemType;
typedef struct
{
  ElemType data[MAXSIZE];
  int top;
} SqStack;

// 初始化数组
void InitStack(SqStack &s)
{
  s.top = -1;
}

// 入栈
bool Push(SqStack &s, ElemType e)
{
  if (s.top == MAXSIZE - 1)
    return false;
  s.data[++s.top] = e;
  return true;
}

// 出栈
bool Pop(SqStack &s, ElemType &e)
{
  if (s.top == -1)
    return false;
  e = s.data[s.top--];
  return true;
}

// 判空
bool IsEmpty(SqStack &s)
{
  return s.top == -1;
}

// 括号匹配
bool BracketCheck(char str[], int length)
{
  SqStack s;
  InitStack(s);
  for (int i = 0; i < length; i++)
  {
    if (str[i] == '(' || str[i] == '{' || str[i] == '[') // 左括号入栈
    {
      Push(s, str[i]);
    }
    else // 扫描到右括号
    {
      if (IsEmpty(s)) // 如果一开始就出现右括号 则直接匹配失败
        return false;

      ElemType topElem;
      Pop(s, topElem); // 栈顶元素出栈
      if (str[i] == ')' && topElem != '(')
        return false;
      else if (str[i] == '}' && topElem != '{')
        return false;
      else if (str[i] == ']' && topElem != '[')
        return false;
    }
  }

  // 全部匹配完后，栈空则匹配成功
  return IsEmpty(s);
}

int main()
{
  char str[] = {'(', '(', ')', ')', '(', ')'};
  printf("%d\n", BracketCheck(str, sizeof(str)));
  // printf("%d\n", sizeof(str));
}